package DoublePointers.Medium;

import java.util.*;

public class LC0015 {
    /**
     * 利用双指针遍历所有二元组，然后利用哈希查找满足和为0的第3个元素是否存在。
     * 时间复杂度：O(N^2)
     */
    public List<List<Integer>> threeSum(int[] nums) {
        HashMap<Integer, Integer> numIndexMap = new HashMap<>();
        int N = nums.length;
        for (int i = 0; i < N; i++) {
            numIndexMap.put(nums[i], i);
        }

        HashSet<List<Integer>> ret = new HashSet<>();
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                int sum = nums[i] + nums[j];
                Integer third = numIndexMap.get(-sum);
                if (third != null && third != i && third != j) {
                    List<Integer> numTuple = Arrays.asList(nums[i], nums[j], nums[third]);
                    Collections.sort(numTuple);
                    if (ret.contains(numTuple)) continue; // 去除重复的三元组
                    ret.add(numTuple);
                }
            }
        }

        return new ArrayList<>(ret);
    }

    private int[] nNums;

    /**
     * 先将数组排序，用一个指针o从左向右顺序遍历。考察每个数字i时，用额外的两个指针p,q指向其右侧数列的左右边界，然后相向移动，
     * 考察每个可能的组合j,k，判断是否有i+j+k=0。
     * 去重：o,p,q任何一个指针移动时，都可以跳过重复的元素。可以证明，这种算法不会漏解。
     * 这种算法的时间复杂度也是O(N^2)，但是在去重方面会比哈希高效许多。
     */
    public List<List<Integer>> threeSum2(int[] nums) {
        Arrays.sort(nums);
        nNums = nums;
        int N = nums.length;
        List<List<Integer>> ret = new ArrayList<>();

        for (int o = 0; o < N - 2; ) {
            int left = nums[o];
            if (left > 0) break;
            int p = o + 1, q = N - 1;
            while (p < q) {
                int mid = nums[p], right = nums[q];
                int sum = left + mid + right;
                if (sum == 0) {
                    ret.add(Arrays.asList(left, mid, right));
                    while (p < q && nums[p] == mid) p++;
                    while (p < q && nums[q] == right) q--;
                }
                else if (sum < 0) { // 过小，左指针右移
                    while (p < q && nums[p] == mid) p++;
                }
                else {
                    while (p < q && nums[q] == right) q--;
                }
            }
            while (o < N - 2 && nums[o] == left) o++;
        }

        return ret;
    }

    /**
     * 计算指定的若干位置上的数字之和。现已弃用。相比直接利用nums[o]+nums[p]+nums[q]，过多调用此函数将导致性能损失。
     */
    @Deprecated
    public int getSum(int... indices) {
        int sum = 0;
        for (int index : indices) sum += nNums[index];
        return sum;
    }
}
